import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    List<String> ret;
    StringBuilder path;
    Map<Character, String> map;
    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        if(digits.length() == 0){
            return ret;
        }
        map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        dfs(digits, 0);
        return ret;
    }
    public void dfs(String digits, int pos){
        if(path.length() == digits.length()){
            ret.add(path.toString());
            return;
        }

        String tmp = map.get(digits.charAt(pos));
        for(int j = 0; j < tmp.length(); j++){
            path.append(tmp.charAt(j));
            dfs(digits, pos + 1);
            // 回溯
            path.deleteCharAt(path.length() - 1);
        }
    }
}